package codetop;

import java.util.Stack;

public class k_node {
    public static class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
    public static void main(String[] args) {
        ListNode node = new ListNode(1);
        ListNode head = node;
        for (int i = 2; i <= 5; i++) {
            node.next = new ListNode(i);
            node = node.next;
        }
        head = reverseKGroup(head, 2);
        while (head != null){
            System.out.print(head.val + " ");
            head = head.next;
        }
    }

    /**
     * 使用栈
     * @param head
     * @param k
     * @return
     */
    public ListNode reverseKGroup1(ListNode head, int k) {
        if (k == 1)
            return head;
        int num = 0;
        ListNode node = head;
        while (node != null) {
            num++;
            node = node.next;
        }
        node = new ListNode();
        ListNode re = node;
        int n = num / k;
        Stack<ListNode> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            while (stack.size() < k && head != null) {
                stack.push(head);
                head = head.next;
            }
            while (!stack.isEmpty()) {
                node.next = stack.pop();
                node = node.next;
            }
        }
        node.next = head;
        return re.next;
    }

    /**
     * 直接反转
     * @param head
     * @param k
     * @return
     */
    public static ListNode reverseKGroup(ListNode head, int k) {
        if (k == 1)
            return head;
        int num = 0;
        ListNode node = head;
        while (node != null) {
            num++;
            node = node.next;
        }
        node = new ListNode();
        node.next = head;
        ListNode re = node;
        int n = num / k;
        ListNode p = node;
        ListNode c = p.next;
        ListNode ne = c;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < k - 1; j++) {
                ne = c.next;
                c.next = ne .next;
                ne.next = p.next;
                p.next = ne;
            }
            p = c;
            c = c.next;
            ne = c;
        }
        return node.next;
    }

    public static ListNode reverseBetween(ListNode head, int left, int right) {
        if(left == right)
            return head;
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode pre;
        pre = dummy;
        int sum = right - left;
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }

        ListNode c = pre.next;
        ListNode ne = c;
        for (int i = 0; i < sum; i++) {
            ne = c.next;
            c.next = ne.next;
            ne.next = pre.next;
            pre.next = ne;
        }
        return dummy.next;
    }
}
